﻿ using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution121
{
    //使用动态规划思想
    public int MaxProfit(int[] prices)
    {
        int len = prices.Length;
        int[][] dp = new int[len][];
        for(int i = 0; i < len; i++)
        {
            dp[i]=new int[2];
        }
        dp[0][0] = -prices[0];

        dp[0][1]=0;

        for(int i = 1; i < len; i++)
        {
            //当天持有股票，1，前一天持有，2，或者前一天不持有，今天买入
            dp[i][0] = Math.Max(dp[i - 1][0], -prices[i]);
            //当天不持有，1，前一天持有，今天卖出,2,前一天不持有
            dp[i][1] = Math.Max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
        }

        return dp[len - 1][1];

    }
}
class Program121
{

    static void Main121()
    {
        Solution121 solution = new Solution121();
        int[] prices = { 7, 1, 5, 3, 6, 4 };
        int maxProfit = solution.MaxProfit(prices);
        Console.WriteLine("Max Profit: " + maxProfit);
        Console.ReadKey();

    } 
}
